Work done while at Facebook AI Research 35th Conference on Neural Information Processing Systems (NeurIPS 2021) Figure 1: Visualization of various hierarchical training schemas, including sequential KLR, synchronous KLR, synchronous CH, and our new SyKLRBR for 4 levels.

A key problem in statistics, computer science, and statistical physics is to draw samples given access to the probability density function, up to a constant of proportionality. Because it is often hard to draw independent samples from the target distribution directly, Markov Chain Monte Carlo(MCMC) methods are often used instead. However, a common difficulty for typical MCMC methods is that for strongly multimodal distributions, MCMC methods take unreasonably long time to reach stationarity. Parallel tempering is an MCMC algorithm that is widely used in sampling from multimodal distributions. Though highly effective in practice, theoretical guarantees on its performance are limited. Since large spectral gap implies fast mixing, a common way to obtain an upper bound on mixing time is to obtain a lower bound on spectral gap.

In recent years, data streaming has gained prominence due to advances in technologies that enable many applications to generate continuous flows of data. This increases the need to develop algorithms that are able to efficiently process data streams. Additionally, real-time requirements and evolving nature of data streams make stream mining problems, including clustering, challenging research problems. In this paper, we propose a one-pass streaming soft clustering (membership of a point in a cluster is described by a distribution) algorithm which approximates the "soft" version of the k-means objective function. Soft clustering has applications in various aspects of databases and machine learning including density estimation and learning mixture models. We first achieve a simple pseudo-approximation in terms of the "hard" k-means algorithm, where the algorithm is allowed to output more than $k$ centers. We convert this batch algorithm to a streaming one (using an extension of the k-means++ algorithm recently proposed) in the "cash register" model. We also extend this algorithm when the clustering is done over a moving window in the data stream.